﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
/*
题目描述：
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
 
限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
*/
// 方法1——暴力法
/*
思路：
使用两层循环枚举出所有的组合，只要遇到一个组合的和为s就返回。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* twoSum1(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	int* answer = (int*)malloc(2 * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	*returnSize = 2;
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize - 1; i++) {
		for (j = i + 1; j < numsSize; j++) {
			if (nums[i] + nums[j] == target) {
				answer[0] = nums[i];
				answer[1] = nums[j];
				return answer;
			}
		}
	}
	return answer;
}
// 时间复杂度：O(n^2)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分法
/*
思路：
对于每个nums[i]，我们都是用二分查找在nums[i + 1] 到 nums[numsSzie - 1]区间内寻找target - nums[i],
如果找到，就直接返回nums[i]和nums[mid]。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* twoSum2(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	int* answer = (int*)malloc(2 * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	*returnSize = 2;
	int i = 0;
	int left = 0;
	int right = 0;
	int mid = 0;
	for (i = 0; i < numsSize - 1; i++) {
		left = i + 1;
		right = numsSize - 1;
		int d = target - nums[i];
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (nums[mid] < d) {
				left = mid + 1;
			}
			else if (nums[mid] > d) {
				right = mid - 1;
			}
			else {
				answer[0] = nums[i];
				answer[1] = nums[mid];
				return answer;
			}
		}
	}
	return answer;
}
// 时间复杂度：O(nlogn)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法3——双指针
/*
思路：
起初我们让一个指针left指向数组的第一个元素，让一个指针right指向数组的最后一个元素，
如果nums[left] + nums[right] < target，则让left++，使和更大。
如果nums[left] + nums[right] == target，那直接返回nums[left]和nums[rihgt]即可。
如果nums[left] + nums[right] > target，则让right--，使和更小。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* twoSum3(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	int* answer = (int*)malloc(2 * sizeof(int));
	if (NULL == answer) {
		perror("malloc");
		return NULL;
	}
	*returnSize = 2;
	int left = 0;
	int right = numsSize - 1;
	while (left < right) {
		if (nums[left] + nums[right] < target) {
			left++;
		}
		else if (nums[left] + nums[right] > target) {
			right--;
		}
		else {
			answer[0] = nums[left];
			answer[1] = nums[right];
			return answer;
		}
	}
	return answer;
}
// 时间复杂度：O(n)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。